var dataNext;
var dataNear;
var datawalk;
var parameter = [];
var LLVPer = []; // list label permanent
var LLVTemp = []; // list label temporary

var findShortPath = false;

var timeChangeRoute = 15*60;
var velocityBus = 20; // velocity bus = 20km/h
var velocityWalk = 5; // velocity walk = 20km/h

// =================================================================
function setData(dNext, dNear, inputClient, dwalk)
{
	dataNext = dNext;
	dataNear = dNear;
	datawalk = dwalk;
	parameter = inputClient;
	LLVPer = []; LLVTemp = [];
}
function shortTestPath()
{
	// code here
	algorithm();
	if(!findShortPath){
		return null;
	}
	else
	{
		//alert('success');
		var staPrev = LLVPer[LLVPer.length - 1].prevS
		for(var i = LLVPer.length - 2; i >= 0; i--)
		{
			if(staPrev == LLVPer[i].s)
			{
				staPrev = LLVPer[i].prevS;
			}
			else
			{
				LLVPer.splice(i,1);
			}
		}
	}
	return LLVPer;
}

// =================================================================
function algorithm()
{
	// code here
	setLLVPer(parameter[0], 0, 0, 0, 0, 0, 0);
	var LVTCur = {}; LVTCur.s = parameter[0]; LVTCur.t = 0;
	LVTCur.d = 0; LVTCur.p = 0; LVTCur.r = 0; LVTCur.dw = 0;

	$i = 0;
	while(true)
	{
		controlAddLLVTemp(LVTCur.s, LVTCur.t, LVTCur.d, LVTCur.p, LVTCur.r, LVTCur.dw);
		var indexMinLV = choseVer();
		if(indexMinLV === null)
		{
			findShortPath = false;	break;
		}
		var labelTemp = LLVTemp[indexMinLV];
		//console.log('labelTemp', labelTemp);
		// set LVTCur
		LVTCur.s = labelTemp.s; LVTCur.t = labelTemp.t; LVTCur.d = labelTemp.d;
		LVTCur.p = labelTemp.p; LVTCur.r = labelTemp.r; LVTCur.dw = labelTemp.dw;
		setLLVPer(labelTemp.s, labelTemp.t, labelTemp.d, labelTemp.p, labelTemp.prevS, labelTemp.r, labelTemp.dw);
		LLVTemp.splice(indexMinLV,1);
		// condition stop algorithm ================================
		if(LVTCur.s == parameter[1])
		{
			findShortPath = true;	break;
		}
	}
}
// =================================================================
function controlAddLLVTemp(sCur, tCur, dCur, pCur, rCur, dwCur) // OK
{
	// code here
	if(dataNext[sCur])
	{
		var NextTemp = dataNext[sCur];
		while(NextTemp.length > 0)
		{
			var timeNext = 0;
			var priceNext = 0;
			var distanceNext = 0;
			if(rCur != NextTemp[0].route)
			{
				// time , price
				priceNext = 4000;
				timeNext = timeChangeRoute;
			}
			priceNext = priceNext + pCur;
			distanceNext = parseInt(NextTemp[0].distance) + dCur;
			timeNext = timeNext + tCur + parseInt((parseInt(3600*NextTemp[0].distance))/(velocityBus*1000));
			addLLVTemp(NextTemp[0].next, timeNext, distanceNext, priceNext, sCur, NextTemp[0].route, dwCur);
			NextTemp.splice(0,1);
		}
	}
	if(datawalk.length > 0){
		if(dataNear[sCur]){
			var NearTemp = dataNear[sCur];
			while(NearTemp.length > 0)
			{
				if(datawalk[0] >= parseInt(NearTemp[0].distance))
				{
					var walknext = 0;
					var priceNext = 0;
					var timeNext = 0;
					var distanceNext = 0;
					walknext = dwCur + parseInt(NearTemp[0].distance);
					if(walknext <= datawalk[1])
					{
						priceNext = pCur;
						distanceNext = parseInt(NearTemp[0].distance) + dCur;
						timeNext = timeChangeRoute + tCur + parseInt((parseInt(3600*NearTemp[0].distance))/(velocityWalk*1000));
						addLLVTemp(NearTemp[0].near, timeNext, distanceNext, priceNext, sCur, 0, walknext);
					}
				}
				NearTemp.splice(0,1);
			}
		}
	}
}
// =================================================================
function choseVer() // OK
{
	// code here
	var indexMinLV = 0;
	if(LLVTemp.length === 0)
	{
		return null;
	}
	else if(LLVTemp.length == 1)
	{
		return 0;
	}
	else
	{
		for(var i = 0; i < LLVTemp.length; i++)
		{
			var arrTwo = [LLVTemp[i].t, LLVTemp[i].d, LLVTemp[i].p];
			var arrOne = [LLVTemp[indexMinLV].t, LLVTemp[indexMinLV].d, LLVTemp[indexMinLV].p];
			if(compare(arrOne, arrTwo) == 'second')
			{
				indexMinLV = i;
			}
		}
	}
	return indexMinLV;
}
// =================================================================
function setLLVPer(s, t, d, p, prevS, r, dw) // OK
{
	// code here
	var existLLVPer = false;
	if(LLVPer.length > 0)
	{
		for(var i = 0; i < LLVPer.length; i++)
		{
			if(s == LLVPer[i].s)
			{
				existLLVPer = true;
				break;
			}
		}
	}
	if(!existLLVPer)
	{
		var itemLLVPer = {};
		itemLLVPer.s = s; itemLLVPer.t = t; itemLLVPer.d = d;
		itemLLVPer.p = p; itemLLVPer.prevS = prevS; itemLLVPer.r = r;
		itemLLVPer.dw = dw;		LLVPer.push(itemLLVPer);
	}
}
// =================================================================
function addLLVTemp(s, t, d, p, prevS, r, dw) // OK
{
	// code here
	var itemLLVTemp = {};
	itemLLVTemp.s = s; itemLLVTemp.t = t; itemLLVTemp.d = d;
	itemLLVTemp.p = p; itemLLVTemp.prevS = prevS; itemLLVTemp.r = r;
	itemLLVTemp.dw = dw;	LLVTemp.push(itemLLVTemp);
}
// =================================================================
function compare(arrOne, arrTwo) // OK
{
	switch(parameter.length)
	{
		case 3:
			return compareOnePriority(arrOne, arrTwo);
		break;
		case 4:
			return compareTwoPriority(arrOne, arrTwo);
		break;
		case 5:
			return compareThreePriority(arrOne, arrTwo);
		break;
	}
}
// ==============================================
function compareOnePriority(arrOne, arrTwo) // OK
{
	switch(parameter[2])
	{
		case 'st':
			if(arrOne[0] > arrTwo[0])
			{
				return 'second';
			}
			else
				return 'first';
		break;
		case 'sd':
			if(arrOne[1] > arrTwo[1])
			{
				return 'second';
			}
			else
				return 'first';
		break;
		case 'sp':
			if(arrOne[2] > arrTwo[2])
			{
				return 'second';
			}
			else
				return 'first';
		break;
	}
}
// ==============================================
function compareTwoPriority(arrOne, arrTwo) // OK
{
	switch(parameter[2])
	{
		case 'st':
			if(arrOne[0] > arrTwo[0])
			{
				return 'second';
			}
			else if(arrOne[0] < arrTwo[0])
			{
				return 'first';
			}
			else
			{
				switch(parameter[3])
				{
					case 'sd':
						if(arrOne[1] > arrTwo[1])
						{
							return 'second';
						}
						else
						{
							return 'first';
						}
					break;
					case 'sp':
						if(arrOne[2] > arrTwo[2])
						{
							return 'second';
						}
						else
						{
							return 'first';
						}
					break;
				}
			}
		break;
		case 'sd':
			if(arrOne[1] > arrTwo[1])
			{
				return 'second';
			}
			else if(arrOne[1] < arrTwo[1])
			{
				return 'first';
			}
			else
			{
				switch(parameter[3])
				{
					case 'st':
						if(arrOne[0] > arrTwo[0])
						{
							return 'second';
						}
						else
						{
							return 'first';
						}
					break;
					case 'sp':
						if(arrOne[2] > arrTwo[2])
						{
							return 'second';
						}
						else
						{
							return 'first';
						}
					break;
				}
			}
		break;
		case 'sp':
			if(arrOne[2] > arrTwo[2])
			{
				return 'second';
			}
			else if(arrOne[2] < arrTwo[2])
			{
				return 'first';
			}
			else
			{
				switch(parameter[3])
				{
					case 'st':
						if(arrOne[0] > arrTwo[0])
						{
							return 'second';
						}
						else
						{
							return 'first';
						}
					break;
					case 'sd':
						if(arrOne[1] > arrTwo[1])
						{
							return 'second';
						}
						else
						{
							return 'first';
						}
					break;
				}
			}
		break;
	}
}
// ================================================
function compareThreePriority(arrOne, arrTwo) // OK
{
	switch(parameter[2])
	{
		case 'st':
			if(arrOne[0] > arrTwo[0])
			{
				return 'second';
			}
			else if(arrOne[0] < arrTwo[0])
			{
				return 'first';
			}
			else
			{
				switch(parameter[3])
				{
					case 'sd':
						if(arrOne[1] > arrTwo[1])
						{
							return 'second';
						}
						else if(arrOne[1] < arrTwo[1])
						{
							return 'first';
						}
						else
						{
							if(arrOne[2] > arrTwo[2])
							{
								return 'second';
							}
							else
							{
								return 'first';
							}
						}
					break;
					case 'sp':
						if(arrOne[2] > arrTwo[2])
						{
							return 'second';
						}
						else if(arrOne[2] < arrTwo[2])
						{
							return 'first';
						}
						else
						{
							if(arrOne[1] > arrTwo[1])
							{
								return 'second';
							}
							else
							{
								return 'first';
							}
						}
					break;
				}
			}
		break;
		case 'sd':
			if(arrOne[1] > arrTwo[1])
			{
				return 'second';
			}
			else if(arrOne[1] < arrTwo[1])
			{
				return 'first';
			}
			else
			{
				switch(parameter[3])
				{
					case 'st':
						if(arrOne[0] > arrTwo[0])
						{
							return 'second';
						}
						else if(arrOne[0] < arrTwo[0])
						{
							return 'first';
						}
						else
						{
							if(arrOne[2] > arrTwo[2])
							{
								return 'second';
							}
							else
							{
								return 'first';
							}
						}
					break;
					case 'sp':
						if(arrOne[2] > arrTwo[2])
						{
							return 'second';
						}
						else if(arrOne[2] < arrTwo[2])
						{
							return 'first';
						}
						else
						{
							if(arrOne[0] > arrTwo[0])
							{
								return 'second';
							}
							else
							{
								return 'first';
							}
						}
					break;
				}
			}
		break;
		case 'sp':
			if(arrOne[2] > arrTwo[2])
			{
				return 'second';
			}
			else if(arrOne[2] < arrTwo[2])
			{
				return 'first';
			}
			else
			{
				switch(parameter[3])
				{
					case 'st':
						if(arrOne[0] > arrTwo[0])
						{
							return 'second';
						}
						else if(arrOne[0] < arrTwo[0])
						{
							return 'first';
						}
						else
						{
							if(arrOne[1] > arrTwo[1])
							{
								return 'second';
							}
							else
							{
								return 'first';
							}
						}
					break;
					case 'sd':
						if(arrOne[1] > arrTwo[1])
						{
							return 'second';
						}
						else if(arrOne[1] < arrTwo[1])
						{
							return 'first';
						}
						else
						{
							if(arrOne[0] > arrTwo[0])
							{
								return 'second';
							}
							else
							{
								return 'first';
							}
						}
					break;
				}
			}
		break;
	}
}